Méthodes basées sur la programmation dynamique

Dans le cadre de l'apprentissage par renforcement, l'utilisation de méthodes de programmation dynamiques permet de calculer les solutions des fonctions de valeurs d'états et d'actions optimales. Cela nous permettra de déterminer par la suite la stratégie que l'agent doit suivre.

Ces méthodes fonctionnent lorsque:

• Le MDP possède un nombre fini et restreint d'états
• Le modèle de l'environnement est parfaitement connu

Nous allons étudier deux algorithmes qui sont:

• L'algorithme par itération des stratégies (Policy Iteration). Cet algorithme comprend deux étapes principales:

  • L'évaluation d'une stratégie (Policy Evaluation)
  • L'amélioration d'une stratégue (Policy Improvement)

• L'algorithme par itération des valeurs (Values Iteration).

5. Algorithme par itération des valeurs

5.1. Algorithme pour les valeurs d'états

Un inconvénient de la méthode par itération des stratégies est qu'elle nécessite d'évaluer la stratégie, ce qui demande beaucoup de calculs car il faut itérer sur l'ensemble des état de l'environnement. La convergence de la séquence des $\{ {V_k}\}$ converge vers $V_\pi$ théoriquement à l'infini.

L'idée de l'algorithme par itération des valeurs est de partir de l'équation optimale de Bellman sur les valeurs d'états:

$${V^*}\left( s \right) = \mathop {\max }\limits_a \sum\limits_{s',r} {p\left( {s',r|s,a} \right)\left[ {r + \gamma {V^*}\left( {s'} \right)} \right]}$$

et de créer une séquence de fonctions convergentes à l'instar de ce qui a été fait sur les {$V_k$} pour évaluer la stratégie:

$${V_{k + 1}} = \mathop {\max }\limits_a \sum\limits_{s',r} {p\left( {s',r|s,a} \right)\left[ {r + \gamma {V_k}\left( {s'} \right)} \right]}$$

On peut montrer que pour une valeur arbitraire de $V_0$, la séquence $\{ {V_k}\}$ converge vers $V^*$.

Pour déterminer la convergence de la séquence, on utlise la même méthode que dans l'évaluation des stratégie. En théorie, la convergence se fait à l'infini et donc on arrête les itérations lorsque les changements sont inférieurs à un petit seuil.

Algorithme pour les valeurs d'états

5.2. Algorithme pour les valeurs des actions

En suivant le même raisonnement mais en s'appuyant cette fois sur l'équation d'optimalité des valeurs d'actions de Bellman:

$${q_*}\left( {s,a} \right) = \sum\limits_{s',r} {p\left( {s',r|s,a} \right)\left[ {r + \gamma \mathop {\max }\limits_{a'} {q_*}\left( {s',a'} \right)} \right]}$$

Et sachant que la valeur d'état est donnée par la relation suivante:

$${V^*}\left( s \right) = \mathop {\max }\limits_a {q_*}\left( {s,a} \right)$$

On peut tirer l'équation de récurence à utiliser pour calculer les valeurs des actions:

$${q_{k + 1}} = \sum\limits_{s',r} {p\left( {s',r|s,a} \right)\left[ {r + \gamma {V_k}\left( {s'} \right)} \right]}$$